/*
 * @(#)Tree.java	1.0 Apr 26, 2008
 *
 *	The MIT License
 *
 *	Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com>
 *
 *	Permission is hereby granted, free of charge, to any person obtaining a copy
 *	of this software and associated documentation files (the "Software"), to deal
 *	in the Software without restriction, including without limitation the rights
 *	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *	copies of the Software, and to permit persons to whom the Software is
 *	furnished to do so, subject to the following conditions:
 *
 *	The above copyright notice and this permission notice shall be included in
 *	all copies or substantial portions of the Software.
 *
 *	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *	THE SOFTWARE.
 */
package org.eoti.util;

import java.util.*;
import java.util.concurrent.*;

/**
 * TreeSet and TreeMap are both Balanced Trees that don't allow duplicate keys.
 * This class is designed to provide a generic tree that allows duplicates.
 */
public class Tree<T extends Tree>
		implements Collection<T>, RandomAccess, Iterable<T>
{
	protected CopyOnWriteArrayList<T> subtrees;

    /**
     * Creates a Symbolic Link to the specified Tree. Changes to one are changed in the other.
     */
	public static <T extends Tree> Tree<T> symlink(Tree<T> tree)
	{
        Tree<T> t = new Tree<T>();
		t.subtrees = tree.subtrees;
		return t;
	}

	/**
	 * Creates a deep copy of the specified Tree. Changes to one do not change the other.
	 */
	public static <T extends Tree> Tree<T> copy(Tree<T> tree)
	{
		Tree<T> t = new Tree<T>();
		t.addAll(tree.subtrees);
		return t;
	}

	public Tree()
	{
        subtrees = new CopyOnWriteArrayList<T>();
	}

	// START OVERRIDES OF Object
	public String toString()
	{
		return String.format("[Tree [%s]]", subtrees.toString());
	}
	// END OVERRIDES OF Object

	// START OVERRIDES OF Collection
	public int size(){return subtrees.size();}
	public boolean isEmpty(){return subtrees.isEmpty();}
	public boolean contains(Object o){return subtrees.contains(o);}
	public Iterator<T> iterator(){return subtrees.iterator();}
	public Object[] toArray(){return subtrees.toArray();}
	public <T> T[] toArray(T[] ts){return subtrees.toArray(ts);}
	public boolean add(T subTree){return subtrees.add(subTree);}
	public boolean remove(Object o){return subtrees.remove(o);}
	public boolean containsAll(Collection<?> c){return subtrees.containsAll(c);}
	public boolean addAll(Collection<? extends T> ts){return subtrees.addAll(ts);}
	public boolean removeAll(Collection<?> c){return subtrees.removeAll(c);}
	public boolean retainAll(Collection<?> c){return subtrees.retainAll(c);}
	public void clear(){subtrees.clear();}
	public int hashCode(){return subtrees.hashCode();}
	public boolean equals(Object obj)
	{
		if(!(obj instanceof Tree))
			return false;

		return subtrees.equals( ((Tree)obj).subtrees );
	}
    // END OVERRIDES OF Collection

	// START WRAPPERS OF CopyOnWriteArrayList
	public void add(int index, T subTree){subtrees.add(index,subTree);}
	public T get(int index){return subtrees.get(index);}
	public int indexOf(T subTree, int index){return subtrees.indexOf(subTree,index);}
	public int indexOf(Object obj){return subtrees.indexOf(obj);}
	public int lastIndexOf(T subTree, int index){return subtrees.lastIndexOf(subTree,index);}
	public int lastIndexOf(Object obj){return subtrees.lastIndexOf(obj);}
	public ListIterator<T> listIterator(){return subtrees.listIterator();}
	public ListIterator<T> listIterator(int index){return subtrees.listIterator(index);}
    public T remove(int index){return subtrees.remove(index);}
	public T set(int index, T subTree){return subtrees.set(index,subTree);}
	public List<T> subList(int fromIndex, int toIndex){return subtrees.subList(fromIndex,toIndex);}
    // END WRAPPERS OF CopyOnWriteArrayList

	public Tree<T> copy(){return copy(this);}
}
